package br.ufmg.vod.wbr.algorithims.components;

import java.util.Arrays;

import javolution.util.FastList;
import junit.framework.TestCase;
import br.ufmg.vod.test.TestConfig;
import br.ufmg.vod.wbr.algorithims.bfs.FastBFS;
import br.ufmg.vod.wbr.graphs.FastDirectedGraph;
import br.ufmg.vod.wbr.graphs.IDXGraphLoader;

public class StronglyConnectedComponentsDFSTest extends TestCase {

	private FastDirectedGraph directedGraph;
	private FastList<int[]> sccs;
	
	
	@Override
	protected void setUp() throws Exception {
		directedGraph = new IDXGraphLoader(TestConfig.inLinkIdx, TestConfig.inLink, TestConfig.outLinkIdx, TestConfig.outLink, TestConfig.sample, TestConfig.sampleSize).loadGraph();
		super.setUp();
	}

	public void testRun() {
		StronglyConnectedComponentsDFS sccAlgorithms = new StronglyConnectedComponentsDFS(directedGraph);
		sccAlgorithms.run();
		sccs = sccAlgorithms.getComponents();
		for (int[] scc : sccs) {
			for (int source : scc) {
				FastBFS bfs = new FastBFS(directedGraph);
				bfs.bfsSingleVertex(source);
				int[] visited = bfs.getData().visitedQueue.toArray(new int[bfs.getData().visitedQueue.size()]);
				Arrays.sort(visited);
				assertTrue( visited.length >= scc.length );
				for (int vertex : scc) {
					assertTrue( Arrays.binarySearch(visited, vertex) != -1);
				}
			}
		}
	}

}
